{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Common Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestCommonSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长公共子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串 <code>text1</code> 和 <code>text2</code>，返回这两个字符串的最长 <strong>公共子序列</strong> 的长度。如果不存在 <strong>公共子序列</strong> ，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>一个字符串的 <strong>子序列</strong><em> </em>是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"ace\"</code> 是 <code>\"abcde\"</code> 的子序列，但 <code>\"aec\"</code> 不是 <code>\"abcde\"</code> 的子序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>两个字符串的 <strong>公共子序列</strong> 是这两个字符串所共同拥有的子序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text1 = \"abcde\", text2 = \"ace\" \n",
    "<strong>输出：</strong>3  \n",
    "<strong>解释：</strong>最长公共子序列是 \"ace\" ，它的长度为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text1 = \"abc\", text2 = \"abc\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最长公共子序列是 \"abc\" ，它的长度为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text1 = \"abc\", text2 = \"def\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>两个字符串没有公共子序列，返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= text1.length, text2.length <= 1000</code></li>\n",
    "\t<li><code>text1</code> 和 <code>text2</code> 仅由小写英文字符组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-common-subsequence](https://leetcode.cn/problems/longest-common-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-common-subsequence](https://leetcode.cn/problems/longest-common-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcde\"\\n\"ace\"', '\"abc\"\\n\"abc\"', '\"abc\"\\n\"def\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        return sorted(reduce(lambda x, y: set(x) & set(y), arrays))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # set\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        cur = set(arrays[0])\n",
    "        for i in range(1, len(arrays)):\n",
    "            cur &= set(arrays[i])\n",
    "\n",
    "        return sorted(list(cur))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        res = set(arrays[0])\n",
    "        for array in arrays[1:]:\n",
    "            res = res.intersection(array)\n",
    "        return sorted(list(res))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        counter = [0] * 101\n",
    "        n = len(arrays)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            for j in arrays[i]:\n",
    "                counter[j] += 1\n",
    "        for i in range(101):\n",
    "            if counter[i] == n: res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        n = len(arrays)\n",
    "        counter = Counter(arrays[0])\n",
    "        for i in range(1, n):\n",
    "            counter += Counter(arrays[i])\n",
    "        filter_counter = list(filter(lambda x: x[1] == n, counter.items()))\n",
    "        return [x[0] for x in filter_counter]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        cur = set(arrays[0])\n",
    "        for i in range(1,len(arrays)):\n",
    "            cur &= set(arrays[i])\n",
    "\n",
    "        if not cur:\n",
    "            return []\n",
    "\n",
    "        return sorted(list(cur))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        counter = defaultdict(int)\n",
    "        for arr in arrays:\n",
    "            for it in arr:\n",
    "                counter[it] += 1\n",
    "        result = list()\n",
    "        n = len(arrays)\n",
    "        for i in range(1, 101):\n",
    "            if counter[i] == n:\n",
    "                result.append(i)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        return sorted(reduce(lambda x, y: x & y, map(set,arrays)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # set\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        cur = set(arrays[0])\n",
    "        for i in range(1,len(arrays)):\n",
    "            cur &= set(arrays[i])\n",
    "\n",
    "        return sorted(list(cur))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        n=len(arrays)\n",
    "        for i in range(1,101):\n",
    "            check=True\n",
    "            for j in range(n):\n",
    "                m=len(arrays[j])\n",
    "                temp=bisect_left(arrays[j],i)\n",
    "                if temp>=m or arrays[j][temp]!=i:\n",
    "                    check=False\n",
    "            if check:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "\n",
    "        dp=[[0]*100 for i in range(len(arrays))]\n",
    "\n",
    "        for i in range(len(arrays)):\n",
    "            for j in arrays[i]:\n",
    "                dp[i][j-1]=1\n",
    "        result=[]\n",
    "        for j in range(100):\n",
    "            num=0\n",
    "            for i in range(len(arrays)):\n",
    "                num+=dp[i][j]\n",
    "            if num==len(arrays):\n",
    "                result.append(j+1)\n",
    "\n",
    "        return result\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        for arr in arrays:\n",
    "            if not arr:\n",
    "                return []\n",
    "        n = len(arrays)\n",
    "        if n == 1:\n",
    "            return arrays[0]\n",
    "        elif n == 2:\n",
    "            arr1,arr2 = arrays[0], arrays[1]\n",
    "            n1,n2 = len(arr1), len(arr2)\n",
    "            i=j = 0\n",
    "            ans = []\n",
    "            while i < n1 and j<n2:\n",
    "                if arr1[i] < arr2[j]:\n",
    "                    i += 1\n",
    "                elif arr1[i] == arr2[j]:\n",
    "                    ans.append(arr1[i])\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return ans \n",
    "        else:\n",
    "            return self.longestCommonSubsequence([self.longestCommonSubsequence(arrays[:n//2]), self.longestCommonSubsequence(arrays[n//2:])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "\n",
    "        cnts = [0] * 101\n",
    "        for arr in arrays:\n",
    "            for num in arr:\n",
    "                cnts[num] += 1\n",
    "\n",
    "        n = len(arrays)\n",
    "        return [i for i in range(1,101) if cnts[i] == n]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def find(arr1, arr2):\n",
    "            n1,n2 = len(arr1), len(arr2)\n",
    "            i=j = 0\n",
    "            ans = []\n",
    "            while i < n1 and j<n2:\n",
    "                if arr1[i] < arr2[j]:\n",
    "                    i += 1\n",
    "                elif arr1[i] == arr2[j]:\n",
    "                    ans.append(arr1[i])\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return ans \n",
    "        \n",
    "        cur = arrays[0]\n",
    "        for arr in arrays[1:]:\n",
    "            cur = find(cur, arr)\n",
    "            if not cur:\n",
    "                break  \n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        a=[j for i in arrays for j in i]\n",
    "        b=collections.Counter(a)\n",
    "        result=[]\n",
    "        for key in b:\n",
    "            if b[key]==len(arrays):\n",
    "                result.append(key)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = [[0]*(len(text1)+1) for i in range(len(text2)+1)]\n",
    "        \n",
    "        for j in range(len(text1)-1, -1, -1):\n",
    "            for i in range(len(text2)-1, -1, -1):\n",
    "                if text2[i] == text1[j]:\n",
    "                    dp[i][j] = dp[i+1][j+1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j+1])\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, s: str, t: str) -> int:\n",
    "        m,n = len(s),len(t)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(m):\n",
    "            new = [0]*(n+1)\n",
    "            for j in range(n):\n",
    "                if s[i] == t[j]:\n",
    "                    new[j+1] = dp[j] + 1\n",
    "                else:\n",
    "                    new[j+1] = max(dp[j+1],new[j])\n",
    "            dp = new\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp_last = [0] * (len(text1) + 1)\n",
    "        dp = [0] * (len(text1) + 1)\n",
    "\n",
    "        for i in range(len(text2)):\n",
    "            for j in range(1, len(text1)+1):\n",
    "                if text2[i]==text1[j-1]:\n",
    "                    dp[j] = dp_last[j-1]+1\n",
    "                else:\n",
    "                    dp[j] = max(dp[j-1], dp_last[j])\n",
    "            dp_last = deepcopy(dp)\n",
    "            # print(dp,dp_last)\n",
    "            \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "\n",
    "        dp=[[0]*(len(text1)+1) for _ in range(len(text2)+1)]\n",
    "        \n",
    "        for i in range(1,len(text2)+1):\n",
    "            for j in range(1,len(text1)+1):\n",
    "                \n",
    "                if text2[i-1]==text1[j-1]:\n",
    "                    dp[i][j]=max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]+1)\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i][j-1],dp[i-1][j])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n1 = len(text1)\n",
    "        n2 = len(text2)\n",
    "\n",
    "        dp = [[0] * (n2+1) for _ in range(n1+1)]\n",
    "\n",
    "        for i in range(1, n1+1):\n",
    "            for j in range(1, n2+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1] + 1)\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1],dp[i-1][j])\n",
    "\n",
    "        return dp[-1][-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "       m = len(text1)\n",
    "       n = len(text2)\n",
    "       self.temp = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "       return self.dp3(text1 , 0 , text2 , 0)\n",
    "    \n",
    "    \n",
    "    def dp3(self , str1, i, str2, j):\n",
    "        if i == len(str1) or j == len(str2):\n",
    "            return 0\n",
    "        \n",
    "        if self.temp[i][j] != -1:\n",
    "            return self.temp[i][j]\n",
    "        \n",
    "        if str1[i] == str2[j]:\n",
    "            # 已经找到一个相同的字符\n",
    "            self.temp[i][j] = 1 + self.dp3(str1, i + 1, str2, j + 1)\n",
    "        else:\n",
    "            # s1[i]和s2[j]中至少有一个字符不在lcs中，\n",
    "            # 穷举三种情况的结果，取其中的最大结果\n",
    "            self.temp[i][j] = max(\n",
    "                # 情况一、s1[i] 不在 lcs 中\n",
    "                self.dp3(str1, i + 1, str2, j),\n",
    "                # 情况二、s2[j] 不在 lcs 中\n",
    "                self.dp3(str1, i, str2, j + 1))\n",
    "            # 情况三、都不在 lcs 中\n",
    "            # dp(str1, i + 1, str2, j + 1))\n",
    "        return self.temp[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        #没办法滑动窗口 直接遍历也会超 考虑dp\n",
    "        m = len(text1)\n",
    "        n = len(text2)\n",
    "\n",
    "        dp = [[0]*(n + 1) for i in range(m + 1)]  #dp[i][j]代表字符text1[:i]与text2[:j]最大公共子序列\n",
    "        for i in range(1,m + 1):\n",
    "            for j in range(1,n + 1):\n",
    "                if text1[i - 1] == text2[j - 1]:\n",
    "                    dp[i][j] = max(dp[i][j - 1],dp[i - 1][j - 1] + 1) #比左斜上方已经遍历完的状态+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j - 1],dp[i - 1][j])   #取左侧or上侧最大的值\n",
    "        return dp[-1][-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = np.zeros((len(text1), len(text2)), dtype = np.int32)\n",
    "        for i in range(len(text1)):\n",
    "            for j in range(len(text2)):\n",
    "                if i == 0 and j == 0:\n",
    "                    dp[i][j] = int(text1[i] == text2[j])\n",
    "                elif i == 0:\n",
    "                    dp[i][j] = max(int(text1[i] == text2[j]),dp[i][j - 1])\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = max(int(text1[i] == text2[j]), dp[i - 1][j])\n",
    "                else:\n",
    "                    dp[i][j] = max(int(text1[i] == text2[j]) + dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])\n",
    "        \n",
    "        return int(dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m = len(text1)\n",
    "        n = len(text2)\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "\n",
    "        for ii in range(1, m + 1):\n",
    "            for jj in range(1, n + 1):\n",
    "                if text1[ii - 1] == text2[jj - 1]:\n",
    "                    dp[ii][jj] = max(dp[ii][jj], dp[ii - 1][jj - 1] + 1)\n",
    "                else:\n",
    "                    dp[ii][jj] = max(dp[ii - 1][jj], dp[ii][jj - 1])\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        # dp[i][j]:text1的前i个，text2的前j个，LCS\n",
    "        # 如果两数组的ij元素相等：dp[i][j]=dp[i-1][j-1]+1\n",
    "        # 不相等：dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n",
    "        # dp = [[0] * len(text2) for _ in range(len(text1))]\n",
    "        # \"首元素处理\"\n",
    "        # # i=0\n",
    "        # for j in range(len(text2)):\n",
    "        #     if text1[0] == text2[j]:\n",
    "        #         dp[0][j:]=[1]* (len(text2)-j)\n",
    "        #         break\n",
    "        # # j=0\n",
    "        # for i in range(len(text1)):\n",
    "        #     if text2[0] == text1[i]:\n",
    "        #         for k in range(i,len(text1)):\n",
    "        #             dp[k][0]=1\n",
    "        #         break\n",
    "        dp = [[] for _ in range(len(text1))]\n",
    "        for i in range(len(text1)):\n",
    "            if text1[i]==text2[0]:\n",
    "                dp[i:]=[[1]+[0]*(len(text2)-1) for _ in range(len(text1)-i)]\n",
    "                break\n",
    "            else:\n",
    "                dp[i]=[0]*len(text2)\n",
    "        for j in range(len(text2)):\n",
    "            if text2[j]==text1[0]:\n",
    "                dp[0][j:]=[1]*(len(text2)-j)\n",
    "                break\n",
    "        print(dp)\n",
    "        \"遍历\"\n",
    "        for i in range(1,len(text1)):\n",
    "            for j in range(1,len(text2)):\n",
    "                if text1[i] == text2[j]:\n",
    "                    dp[i][j]=dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\r\n",
    "        m = len(text1)\r\n",
    "        n = len(text2)\r\n",
    "        cache =[[0]*(n+1) for _ in range(m+1)]\r\n",
    "        # @cache\r\n",
    "        def dfs(i,j):\r\n",
    "            if i<0 or j<0:\r\n",
    "                return 0    \r\n",
    "            if cache[i][j] != -1 :\r\n",
    "                return cache[i][j]\r\n",
    "            if text1[i] == text2[j]:              \r\n",
    "                cache[i][j] = dfs(i-1,j-1)+1\r\n",
    "                return cache[i][j]\r\n",
    "            cache[i][j] = max(dfs(i-1,j),dfs(i,j-1)) \r\n",
    "            return cache[i][j]\r\n",
    "        # aaa = dfs(m-1,n-1)\r\n",
    "        \r\n",
    "        for i,x in enumerate(text1):\r\n",
    "            for j,y in enumerate(text2):\r\n",
    "                if x == y:\r\n",
    "                    cache[i+1][j+1] = cache[i][j]+1\r\n",
    "                else:\r\n",
    "                    cache[i+1][j+1] = max(cache[i][j+1], cache[i+1][j])\r\n",
    "        \r\n",
    "        return cache[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = [[ 0 for j in range(len(text2)+1)] for i in range(len(text1)+1)]\n",
    "\n",
    "        for i in range(1, len(text1)+1):\n",
    "            for j in range(1, len(text2)+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        import numpy as np\n",
    "        n1, n2 = len(text1)+1, len(text2)+1\n",
    "        dp = [[0]*n2 for _ in range(n1)]\n",
    "        res = 0\n",
    "        for i in range(1,n1):\n",
    "            for j in range(1,n2):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "                # if dp[i][j]>res:\n",
    "                #     res = dp[i][j]\n",
    "        print(max(max(dp)))\n",
    "        return max(max(dp))\n",
    "        # n1,n2 = len(text1)+1, len(text2)+1\n",
    "        # dp = [[0]*n2 for _ in range(n1)]\n",
    "        # res = 0\n",
    "        # for i in range(1,n1):\n",
    "        #     for j in range(1,n2):\n",
    "        #         if text1[i-1] ==text2[j-1]:\n",
    "        #             dp[i][j] = dp[i-1][j-1]+1\n",
    "        #         else:\n",
    "        #             dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "        #         if dp[i][j] > res:\n",
    "        #             res = dp[i][j]\n",
    "        # return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = np.zeros((len(text1)+1, len(text2)+1), dtype=int).tolist()\n",
    "        for i in range(1, len(text1)+1):\n",
    "            for j in range(1, len(text2)+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1],dp[i-1][j])\n",
    "\n",
    "        return dp[len(text1)][len(text2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n = len(text1)\n",
    "        m = len(text2)\n",
    "        res = 0\n",
    "        tokens = []\n",
    "        dp = [[0 for i in range(n + 1)] for j in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if text2[i - 1] == text1[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                    tokens.append(text1[j - 1])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "                res = max(res, dp[i][j])\n",
    "        print(dp)\n",
    "        print(tokens)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = np.zeros((len(text1)+1, len(text2)+1), dtype=int).tolist()\n",
    "        for i in range(1, len(text1)+1):\n",
    "            for j in range(1, len(text2)+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i][j-1],dp[i-1][j])\n",
    "\n",
    "        return dp[len(text1)][len(text2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "#         dp = [[0 for i in range(s2_length)] for i in range(s1_length)]\n",
    "#\n",
    "#         for k in range(s2_length):\n",
    "#             if s1[0] in s2[:k+1]:\n",
    "#                 dp[0][k] = 1\n",
    "#\n",
    "#         for k in range(s1_length):\n",
    "#             if s2[0] in s1[:k+1]:\n",
    "#                 dp[k][0] = 1\n",
    "#\n",
    "#         for i in range(1, s1_length):\n",
    "#             for j in range(1, s2_length):\n",
    "#                 if s1[i] == s2[j]:\n",
    "#                     dp[i][j] = dp[i-1][j-1] + 1\n",
    "#                 else:\n",
    "#                     dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])\n",
    "#\n",
    "#         return dp[s1_length-1][s2_length-1]\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "\n",
    "        length1 = len(text1)\n",
    "        length2 = len(text2)\n",
    "        targetString = text1+text2[::-1]\n",
    "        lengthTarget = length1+length2\n",
    "    \n",
    "        dp = [[0 for x in range(lengthTarget)] for x in range(lengthTarget)]\n",
    "    \n",
    "        for i in range(length1-1, -1, -1):\n",
    "            for j in range(length1, lengthTarget):\n",
    "                if i == length1-1 or j == length1:\n",
    "                    if targetString[i] == targetString[j]:\n",
    "                        dp[i][j] = 2\n",
    "                        continue\n",
    "                if targetString[i] == targetString[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "        return dp[0][lengthTarget-1]//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.mem = {}\n",
    "        return self.search(text1, text2, 0, 0)\n",
    "    \n",
    "    def search(self, text1, text2, i, j):\n",
    "        if i not in self.mem:\n",
    "            self.mem[i] = {}\n",
    "        \n",
    "        if j in self.mem[i]:\n",
    "            return self.mem[i][j]\n",
    "            \n",
    "        if i >= len(text1) or j >= len(text2):\n",
    "            return 0\n",
    "        \n",
    "        if text1[i] == text2[j]:\n",
    "            self.mem[i][j] = self.search(text1, text2, i + 1, j + 1) + 1\n",
    "            return self.mem[i][j]\n",
    "        else:\n",
    "            self.mem[i][j] = max(self.search(text1, text2, i + 1, j), self.search(text1, text2, i, j + 1))\n",
    "            return self.mem[i][j]\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.stats import truncnorm\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m = len(text1)\n",
    "        n = len(text2)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        res = lcs(text1, text2)\n",
    "        # return len(res)\n",
    "        return res\n",
    "\n",
    "\n",
    "#最长公共子序列\n",
    "def lcs(s1, s2):\n",
    "    m = len(s1)\n",
    "    n = len(s2)\n",
    "    # 定义一个二维数组，用来保存子序列\n",
    "    # 数组元素为空列表\n",
    "    dp = [[[] for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "    # 初始化第一行和第一列\n",
    "    for i in range(m + 1):\n",
    "        for j in range(n + 1):\n",
    "            if i == 0 or j == 0:\n",
    "                dp[i][j] = 0\n",
    "            else:\n",
    "                if s1[i - 1] == s2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + len(s1[i - 1])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "    return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, text1, text2, pos1, pos2, res_dict, char_indexs1, char_indexs2):\n",
    "        if (pos1, pos2) in res_dict:\n",
    "            return res_dict[(pos1, pos2)]\n",
    "\n",
    "        if pos1 == -1 or pos2 == -1:\n",
    "            return 0\n",
    "        \n",
    "        if text1[pos1] == text2[pos2]:\n",
    "            res_dict[(pos1, pos2)] = 1 + self.search(text1, text2, pos1 - 1, pos2 - 1, res_dict, char_indexs1, char_indexs2)\n",
    "            return res_dict[(pos1, pos2)]\n",
    "        \n",
    "        temp_len = 0\n",
    "        for i in char_indexs1.get(text2[pos2], []):\n",
    "            if i < pos1:\n",
    "                temp_len = max(temp_len, self.search(text1, text2, i - 1, pos2 - 1, res_dict, char_indexs1, char_indexs2) + 1)\n",
    "                break\n",
    "        for i in char_indexs2.get(text1[pos1], []):\n",
    "            if i < pos2:\n",
    "                temp_len = max(temp_len, self.search(text1, text2, pos1 - 1, i - 1, res_dict, char_indexs1, char_indexs2) + 1)\n",
    "                break\n",
    "        temp_len = max(temp_len, self.search(text1, text2, pos1 - 1, pos2 - 1, res_dict, char_indexs1, char_indexs2))\n",
    "        res_dict[(pos1, pos2)] = temp_len\n",
    "        return res_dict[(pos1, pos2)]\n",
    "\n",
    "\n",
    "\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        length1, length2 = len(text1), len(text2)\n",
    "        char_indexs1 = {}\n",
    "        char_indexs2 = {}\n",
    "        for i in range(length1 - 1, -1, -1):\n",
    "            temp = char_indexs1.get(text1[i], [])\n",
    "            temp.append(i)\n",
    "            char_indexs1[text1[i]] = temp\n",
    "        for i in range(length2 - 1, -1, -1):\n",
    "            temp = char_indexs2.get(text2[i], [])\n",
    "            temp.append(i)\n",
    "            char_indexs2[text2[i]] = temp\n",
    "        return self.search(text1, text2, length1 - 1, length2 - 1, {}, char_indexs1, char_indexs2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   \n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        seq = {}\n",
    "        seq[len(text1)] = {k:0 for k in range(0,len(text2)+1)}\n",
    "        for i in range(len(text1)-1,-1,-1):\n",
    "            seq[i] = {len(text2):0}\n",
    "            for j in range(len(text2)-1,-1,-1):\n",
    "                \n",
    "                if text1[i] == text2[j]:\n",
    "                    seq[i][j] = 1 + seq[i+1][j+1]\n",
    "                else:\n",
    "                    seq[i][j] = max(seq[i+1][j], seq[i][j+1])\n",
    "\n",
    "        return seq[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, text1: str, text2: str, i1: int, i2: int) -> int:\n",
    "        key = i1 * (len(text2) + 1) + i2\n",
    "        # print(\"key: \", key, i1, i2)\n",
    "        if key in self.memo:\n",
    "            return self.memo[key]\n",
    "\n",
    "        if i1 == len(text1) or i2 == len(text2):\n",
    "            return 0\n",
    "\n",
    "        result = 0\n",
    "        if text1[i1] == text2[i2]:\n",
    "            result = self.dfs(text1, text2, i1 + 1, i2 + 1) + 1\n",
    "            # print(\"match: \", text1[i1], i1, i2)\n",
    "        # else:\n",
    "        result = max(result, self.dfs(text1, text2, i1 + 1, i2), \\\n",
    "            self.dfs(text1, text2, i1, i2 + 1))\n",
    "        \n",
    "        # print(i1, i2, result)\n",
    "        self.memo[key] = result\n",
    "        return result\n",
    "\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.memo = {}\n",
    "        return self.dfs(text1, text2, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m=len(text1)\n",
    "        n=len(text2)\n",
    "        dp=[[[0,None] for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if text1[i-1]==text2[j-1]:\n",
    "                    dp[i][j][0]=dp[i-1][j-1][0]+1\n",
    "                    dp[i][j][1]=1\n",
    "                else:\n",
    "                    dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j-1][0])\n",
    "                    if dp[i][j][0]==dp[i][j-1][0]:\n",
    "                        dp[i][j][1]=2\n",
    "                    elif dp[i][j][0]==dp[i-1][j][0]:\n",
    "                        dp[i][j][1]=3\n",
    "                    else:\n",
    "                        dp[i][j][1]=0\n",
    "        res=[]\n",
    "        i=m\n",
    "        j=n\n",
    "        while i<m+1 and i>0 and j<n+1 and j>0:\n",
    "                if dp[i][j][1]==1:\n",
    "                    res.append(text1[i-1])\n",
    "                    i-=1\n",
    "                    j-=1\n",
    "                elif dp[i][j][1]==0:\n",
    "                    i-=1\n",
    "                    j-=1\n",
    "                elif dp[i][j][1]==2:\n",
    "                    j-=1\n",
    "                elif dp[i][j][1]==3:\n",
    "                    i-=1\n",
    "        print(''.join(res[::-1]))\n",
    "\n",
    "        return dp[m][n][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "\n",
    "\n",
    "        '''tmp = ''\n",
    "        for i in text1:\n",
    "            if i in text2:\n",
    "                tmp+=i\n",
    "        text1 = tmp\n",
    "\n",
    "        tmp = ''\n",
    "        for i in text2:\n",
    "            if i in text1:\n",
    "                tmp+=i\n",
    "        text2 = tmp'''\n",
    "        m1 = len(text1)\n",
    "        m2 = len(text2)\n",
    "        print(text2)\n",
    "        print(text1)\n",
    "        ans = 0\n",
    "        res  = [[[0,-1] for _ in range(m2)] for _ in range(m1)]\n",
    "        for i in range(m2):\n",
    "            if text1[0]==text2[i]:\n",
    "                for j in range(i,m2):\n",
    "                    res[0][j] = [1,i]\n",
    "                ans = max(ans,1)\n",
    "\n",
    "                break\n",
    "        for j in range(m2):\n",
    "            for i in range(1,m1):\n",
    "                s = text2[res[i-1][j][1]+1:j+1]\n",
    "                ss = text1[i]\n",
    "                if  text1[i] in text2[res[i-1][j][1]+1:j+1]:\n",
    "                    tmp = text2[res[i-1][j][1]+1:j+1]\n",
    "                    ids = tmp.find(text1[i])\n",
    "                    res[i][j] = [res[i-1][j][0]+1,res[i-1][j][1]+ids+1]\n",
    "                    ans = max(ans,res[i][j][0])\n",
    "                else:\n",
    "                    res[i][j] = res[i-1][j] if j>0 and res[i-1][j][0] > res[i][j-1][0]  else res[i][j-1]\n",
    "        # [print(res[i]) for i in range(m1)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, a: str, b: str) -> int:\n",
    "        m = len(a)\n",
    "        n = len(b)\n",
    "        cache = [[-1] * (m + n) for _ in range(n + m)]\n",
    "        def dfs(i, j):\n",
    "            if cache[i][j] != -1: return cache[i][j]\n",
    "            if i < 0 or j < 0: return 0\n",
    "            if a[i] == b[j]: return dfs(i - 1, j - 1) + 1\n",
    "            ans = max(dfs(i - 1, j), dfs(i, j - 1))\n",
    "            cache[i][j] = ans\n",
    "            return ans\n",
    "        ans = dfs(m - 1, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.lru_cache(100000)\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        if text1 == '' or text2 == '':\n",
    "            return 0\n",
    "\n",
    "        if text1[0] == text2[0]:\n",
    "            return 1 + self.longestCommonSubsequence(text1[1:], text2[1:])\n",
    "        else:\n",
    "            return max(self.longestCommonSubsequence(text1[1:], text2), self.longestCommonSubsequence(text1, text2[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, l1: str, l2: str) -> int:\n",
    "        dp = [[-1 for _ in range(1000)] for _ in range(1000)]\n",
    "        def lcs(l1, l2):\n",
    "            if dp[len(l1)][len(l2)] != -1:\n",
    "                return dp[len(l1)][len(l2)]\n",
    "            if len(l1) == 0 or len(l2) == 0:\n",
    "                dp[len(l1)][len(l2)] = 0\n",
    "                return 0\n",
    "            if l1[-1] == l2[-1]:\n",
    "                dp[len(l1)][len(l2)] = lcs(l1[:-1], l2[:-1]) + 1\n",
    "                return lcs(l1[:-1], l2[:-1]) + 1\n",
    "            dp[len(l1)][len(l2)] = max(\n",
    "                lcs(l1[:-1], l2),\n",
    "                lcs(l1, l2[:-1])\n",
    "            )\n",
    "            return dp[len(l1)][len(l2)]\n",
    "        return lcs(l1, l2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        l1 = len(text1)\n",
    "        l2 = len(text2)\n",
    "        dp = [[[0, 0] for _ in range(l1)] for _ in range(l2)]\n",
    "        for j in range(l2):\n",
    "            for i in range(l1):\n",
    "                left = dp[j][i - 1][1] if i > 0 else 0\n",
    "                top = dp[j - 1][i][1] if j > 0 else 0\n",
    "                max_num = dp[j - 1][i - 1][1] if i > 0 and j > 0 else 0\n",
    "                if text1[i] == text2[j]:\n",
    "                    max_num += 1\n",
    "                    dp[j][i][0] = max_num\n",
    "                dp[j][i][1] = max(left, top, max_num)\n",
    "        return dp[-1][-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n1 = len(text1)\n",
    "        n2 = len(text2)\n",
    "        memo = {}\n",
    "        def dp(i,j):\n",
    "            if i>=n1 or j>=n2:\n",
    "                return 0\n",
    "            key = str(i)+'&'+str(j)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            temp1 = 0\n",
    "            temp2 = 0\n",
    "            if text1[i] == text2[j]:\n",
    "                temp1 = 1+dp(i+1,j+1)\n",
    "            temp2 = max(dp(i,j+1),dp(i+1,j))\n",
    "            temp = max(temp1,temp2)\n",
    "            memo[key] = temp\n",
    "            return temp\n",
    "        return dp(0,0)\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = [[0 for i in range(1001)] for j in range(1001)]\n",
    "        vis = [[0 for i in range(1001)] for j in range(1001)]\n",
    "        l1,l2 = len(text1),len(text2)\n",
    "        for i in range(1,l1+1):\n",
    "            for j in range(1,l2+1):\n",
    "                if text1[i-1]==text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                    vis[i][j]=1\n",
    "                else:\n",
    "                    if dp[i-1][j]>dp[i][j-1]:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                        vis[i][j] = 2\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j-1]\n",
    "                        vis[i][j] = 3\n",
    "        box = []\n",
    "        def fun(i,j):\n",
    "            if vis[i][j]==1:\n",
    "                fun(i-1,j-1)\n",
    "                box.append(text1[i-1])\n",
    "            elif vis[i][j]==2:\n",
    "                fun(i-1,j)\n",
    "            else:\n",
    "                fun(i,j-1)\n",
    "        print(box)\n",
    "        return dp[l1][l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        mem = {}\n",
    "\n",
    "        def find(text1, text2, i, j):\n",
    "            nonlocal mem\n",
    "            if i not in mem:\n",
    "                mem[i] = {}\n",
    "            \n",
    "            if j in mem[i]:\n",
    "                return mem[i][j]\n",
    "            \n",
    "            if i >= len(text1) or j >= len(text2):\n",
    "                return 0\n",
    "            \n",
    "            if text1[i] == text2[j]:\n",
    "                mem[i][j] = find(text1, text2, i + 1, j + 1) + 1\n",
    "                return mem[i][j]\n",
    "            else:\n",
    "                mem[i][j] = max(find(text1, text2, i + 1, j), find(text1, text2, i, j + 1))\n",
    "                return mem[i][j]\n",
    "            \n",
    "        return find(text1, text2, 0, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]\n",
    "        for i, j in [(i, j) for i in range(len(text1) + 1) for j in range(len(text2) + 1)]:\n",
    "            if i == 0 or j == 0:\n",
    "                dp[i][j] = 0\n",
    "            else:\n",
    "                if text1[i - 1] == text2[j - 1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if not i or not j:\n",
    "                return 0\n",
    "            if t1[i-1] == t2[j-1]:\n",
    "                return dfs(i-1, j-1) + 1\n",
    "            return max(dfs(i-1,j), dfs(i, j-1))\n",
    "        # 获取两个字符串的字符集合\n",
    "        set1, set2 = set(text1), set(text2)\n",
    "        # 获取公共字符集合\n",
    "        common_chars = set1 & set2\n",
    "        # 删除非公共字符\n",
    "        filtered_text1 = [c for c in text1 if c in common_chars]\n",
    "        filtered_text2 = [c for c in text2 if c in common_chars]\n",
    "        t1, t2 = filtered_text1, filtered_text2\n",
    "        return dfs(len(filtered_text1), len(filtered_text2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "最长 \n",
    "公共\n",
    "子序列\n",
    "\n",
    "abc\n",
    "ace\n",
    "\n",
    "abc\n",
    "adb\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n, m = len(text1), len(text2)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            \n",
    "            if text1[i] == text2[j]:\n",
    "                return 1 + dfs(i-1, j-1)\n",
    "            \n",
    "            return max(dfs(i, j-1), dfs(i-1, j-1),dfs(i-1, j))\n",
    "            \n",
    "        return dfs(n-1,m-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.l1 = len(text1)\n",
    "        self.l2 = len(text2)\n",
    "        self.memo = {(i,j):-1 for i in range(self.l1+1) for j in range(self.l2+1)}\n",
    "        self.dp(text1,0,text2,0)\n",
    "        # print(self.memo)\n",
    "        return self.memo[(0,0)]\n",
    "\n",
    "    # 这里的教训是最后一位确实没有处理好\n",
    "    def dp(self,s1,i,s2,j):\n",
    "        # i,j 表示从i,j开始到s1和s2末尾的字符串的公共长度；\n",
    "        if i == self.l1 or j == self.l2:\n",
    "            self.memo[(i,j)] = 0\n",
    "            return 0\n",
    "        if self.memo[(i,j)]!=-1:\n",
    "            return self.memo[(i,j)]\n",
    "        if s1[i] == s2[j]:\n",
    "            if self.memo[(i+1,j+1)]==-1:\n",
    "                self.memo[(i+1,j+1)] = self.dp(s1,i+1,s2,j+1)\n",
    "            self.memo[(i,j)] = self.memo[(i+1,j+1)] + 1\n",
    "        else:\n",
    "            self.memo[(i,j)] = max(self.dp(s1,i+1,s2,j),self.dp(s1,i,s2,j+1))\n",
    "        return self.memo[(i,j)]\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self, text1, text2, i, j):\n",
    "        if i==len(text1) or j==len(text2):\n",
    "            return 0\n",
    "        \n",
    "        if (i+1, j+1) not in self.memo:\n",
    "            self.memo[(i+1, j+1)] = self.dp(text1, text2, i+1, j+1)\n",
    "        if (i+1, j) not in self.memo:\n",
    "            self.memo[(i+1, j)] = self.dp(text1, text2, i+1, j)\n",
    "        if (i, j+1) not in self.memo:\n",
    "            self.memo[(i, j+1)] = self.dp(text1, text2, i, j+1)\n",
    "\n",
    "        if text1[i] == text2[j]:\n",
    "            return self.memo[(i+1, j+1)] + 1\n",
    "\n",
    "        return max(\n",
    "            self.memo[(i+1, j)],\n",
    "            self.memo[(i, j+1)]\n",
    "        )\n",
    "\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.memo = {}\n",
    "        return self.dp(text1, text2, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,text1,text2):\n",
    "            if not i or not j:\n",
    "                return 0\n",
    "            if text1[i-1] == text2[j-1]:\n",
    "                return dfs(i-1,j-1,text1,text2)+1\n",
    "            else:\n",
    "                return max(dfs(i-1,j,text1,text2),dfs(i,j-1,text1,text2))\n",
    "\n",
    "        return dfs(len(text1),len(text2),text1,text2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.d = {}\n",
    "        res = self.dp(text1, len(text1)-1, text2, len(text2)-1)\n",
    "        return res\n",
    "\n",
    "    def dp(self, text1, i, text2, j):\n",
    "        if i == -1 or j == -1:\n",
    "            return 0\n",
    "        if str(i) + \"_\" + str(j) in self.d:\n",
    "            return self.d[str(i) + \"_\" + str(j)]\n",
    "        if text1[i] == text2[j]:\n",
    "            self.d[str(i) + \"_\" + str(j)] = self.dp(text1, i-1, text2, j-1) + 1\n",
    "            return self.d[str(i) + \"_\" + str(j)]\n",
    "        res1 = self.dp(text1, i-1, text2, j-1)\n",
    "        res2 = self.dp(text1, i, text2, j-1)\n",
    "        res3 = self.dp(text1, i-1, text2, j)\n",
    "        res = max(max(res1, res2), res3)\n",
    "        self.d[str(i) + \"_\" + str(j)] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dp = {}\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        text1_idx, text2_idx = len(text1) - 1, len(text2) - 1\n",
    "        key = '%s-%s' % (text1_idx, text2_idx)\n",
    "        if key in self.dp.keys():\n",
    "            return self.dp[key]\n",
    "        tmp_sub_seq = 0\n",
    "        while text1_idx >= 0 and text2_idx >= 0:\n",
    "            if text1[text1_idx] == text2[text2_idx]:\n",
    "                tmp_sub_seq = 1 + tmp_sub_seq\n",
    "                text1_idx, text2_idx = \\\n",
    "                    text1_idx - 1, text2_idx - 1\n",
    "            else:\n",
    "                tmp1 = self.longestCommonSubsequence(text1[:text1_idx],\n",
    "                                                text2[:text2_idx+1])\n",
    "                tmp2 = self.longestCommonSubsequence(text1[:text1_idx+1],\n",
    "                                                text2[:text2_idx])\n",
    "                tmp_sub_seq = max(tmp1, tmp2) + tmp_sub_seq\n",
    "                break\n",
    "        self.dp[key] = tmp_sub_seq\n",
    "        return tmp_sub_seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def process(s1, s2, idx1, idx2):\n",
    "            if idx1 == 0 and idx2 == 0:\n",
    "                if s1[idx1] == s2[idx2]:\n",
    "                    return 1\n",
    "                return 0\n",
    "            elif idx1 == 0:\n",
    "                if s1[idx1] == s2[idx2]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return process(s1, s2, idx1, idx2-1)\n",
    "            elif idx2 == 0:\n",
    "                if s1[idx1] == s2[idx2]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return process(s1, s2, idx1-1, idx2)\n",
    "            else:\n",
    "                p1 = process(s1, s2, idx1, idx2-1)\n",
    "                p2 = process(s1, s2, idx1-1, idx2)\n",
    "                p3 = process(s1, s2, idx1-1, idx2-1)\n",
    "\n",
    "                if s1[idx1] == s2[idx2]:\n",
    "                    p4 = 1 + process(s1, s2, idx1-1, idx2-1)\n",
    "                else:\n",
    "                    p4 = 0\n",
    "                \n",
    "                return max(p1, p2, p3, p4)\n",
    "\n",
    "        return process(text1, text2, len(text1)-1, len(text2)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        memo = {}\n",
    "        def dp(i, j):  # text1[0,i]和 text2[0,j]的最长公共字串的长度\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            elif i < 0 or j < 0:\n",
    "                memo[(i, j)] = 0\n",
    "                return 0\n",
    "            elif text1[i] == text2[j]:\n",
    "                t = dp(i - 1, j - 1) + 1\n",
    "                memo[(i, j)] = t\n",
    "                return t\n",
    "            else:\n",
    "                t = max(dp(i-1, j), dp(i, j-1))\n",
    "                memo[(i, j)] = t\n",
    "                return t\n",
    "        res = dp(len(text1)-1, len(text2)-1)\n",
    "        print(memo)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.l1 = len(text1)\n",
    "        self.l2 = len(text2)\n",
    "        self.memo = {(i,j):-1 for i in range(self.l1+1) for j in range(self.l2+1)}\n",
    "        self.dp(text1,0,text2,0)\n",
    "        print(self.memo)\n",
    "        return self.memo[(0,0)]\n",
    "\n",
    "\n",
    "    def dp(self,s1,i,s2,j):\n",
    "        # i,j 表示从i,j开始到s1和s2末尾的字符串的公共长度；\n",
    "        if i == self.l1 or j == self.l2:\n",
    "            self.memo[(i,j)] = 0\n",
    "            return 0\n",
    "        if self.memo[(i,j)]!=-1:\n",
    "            return self.memo[(i,j)]\n",
    "        if s1[i] == s2[j]:\n",
    "            if self.memo[(i+1,j+1)]==-1:\n",
    "                self.memo[(i+1,j+1)] = self.dp(s1,i+1,s2,j+1)\n",
    "            self.memo[(i,j)] = self.memo[(i+1,j+1)] + 1\n",
    "        else:\n",
    "            self.memo[(i,j)] = max(self.dp(s1,i+1,s2,j),self.dp(s1,i,s2,j+1))\n",
    "        return self.memo[(i,j)]\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def check_longest(self, text1, i, text2, j):\n",
    "        if i>=len(text1) or j>=len(text2):\n",
    "            return 0\n",
    "        if (i,j) in self.cache:\n",
    "            return self.cache[(i,j)]\n",
    "        length1 = 0\n",
    "        length2 = 0\n",
    "        if text1[i] == text2[j]:\n",
    "            length1 = 1 + self.check_longest(text1, i+1, text2, j+1)\n",
    "        else:\n",
    "            length2 = max(self.check_longest(text1, i+1, text2, j), self.check_longest(text1, i, text2, j+1))\n",
    "        count = max(length1, length2)\n",
    "        self.cache[(i,j)] = count\n",
    "        return count\n",
    "\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.cache = {}\n",
    "        return self.check_longest(text1, 0, text2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = {}\n",
    "        dp[(0, 0)] = 0\n",
    "        if text1[0] == text2[0]:\n",
    "            dp[(0, 0)] = 1\n",
    "        return self.recursive(len(text1) - 1, len(text2) - 1, text1, text2, dp)\n",
    "\n",
    "    def recursive(self, i, j, text1, text2, dp):\n",
    "        if (i, j) in dp:\n",
    "            return dp[(i, j)]\n",
    "        \n",
    "        seq_len = 0\n",
    "        if text1[i] == text2[j]:\n",
    "            seq_len = 1\n",
    "        \n",
    "        if i - 1 >= 0 and j - 1 >= 0:\n",
    "            seq_len += self.recursive(i - 1, j - 1, text1, text2, dp)\n",
    "        \n",
    "        if i - 1 >= 0:\n",
    "            seq_len = max(seq_len, self.recursive(i - 1, j, text1, text2, dp))\n",
    "\n",
    "        if j - 1 >= 0:\n",
    "            seq_len = max(seq_len, self.recursive(i, j - 1, text1, text2, dp))\n",
    "\n",
    "        dp[(i, j)] = seq_len\n",
    "        return seq_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dptable = {}\n",
    "        for i in range(len(text1)):\n",
    "            dptable[(i,-1)] = 0\n",
    "        for i in range(len(text2)):\n",
    "            dptable[(-1,i)] = 0\n",
    "        dptable[(-1,-1)] = 0\n",
    "        \n",
    "        for i in range(len(text1)):\n",
    "            for j in range(len(text2)):\n",
    "                if text1[i] == text2[j]:\n",
    "                    value = dptable[(i-1,j-1)]+1\n",
    "                else:\n",
    "                    value = max(dptable[(i-1,j)],dptable[(i,j-1)],dptable[(i-1,j-1)])\n",
    "                dptable[(i,j)] = value\n",
    "\n",
    "\n",
    "        return dptable[(len(text1)-1,len(text2)-1)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp = {}\n",
    "        n, m = len(text1), len(text2)\n",
    "        dp[(-1, -1)] = 0\n",
    "        for i in range(n):\n",
    "            dp[(i, -1)] = 0\n",
    "        for i in range(m):\n",
    "            dp[(-1, i)] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if text1[i] == text2[j]:\n",
    "                    dp[(i, j)] = dp[(i-1, j-1)] + 1\n",
    "                else:\n",
    "                    dp[(i, j)] = max( dp[(i, j-1)], dp[(i-1, j)])\n",
    "        \n",
    "        return dp[(n-1, m-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dct1 = defaultdict(list)\n",
    "        if len(text1) < len(text2):\n",
    "            text1, text2 = text2, text1\n",
    "        for i, x1 in enumerate(text1):\n",
    "            dct1[x1].append(i)\n",
    "        pair = set()\n",
    "        for j, x2 in enumerate(text2):\n",
    "            for i in dct1[x2]:\n",
    "                pair.add((i, j))\n",
    "\n",
    "        @functools.lru_cache((len(text1)+1)*(len(text2)+1))\n",
    "        def cnt(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            tmp = cnt(i-1, j-1) + int((i,j) in pair)\n",
    "            if tmp > ans:\n",
    "                ans = tmp\n",
    "            tmp = cnt(i-1, j)\n",
    "            if tmp > ans:\n",
    "                ans = tmp\n",
    "            tmp = cnt(i, j-1)\n",
    "            if tmp > ans:\n",
    "                ans = tmp\n",
    "            return ans\n",
    "\n",
    "        return cnt(len(text1)-1, len(text2)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._memos = {}\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "\n",
    "        if len(text1) == 0 or len(text2) == 0:\n",
    "            return 0\n",
    "        if len(text1) == 1:\n",
    "            if text1 in text2:\n",
    "                return 1\n",
    "            return 0\n",
    "        existed = self._memos.get((len(text1), len(text2)))\n",
    "        if existed is not None:\n",
    "            return existed\n",
    "        end1 = text1[-1]\n",
    "        end2 = text2[-1]\n",
    "        if end1 == end2:\n",
    "            result = self.longestCommonSubsequence(text1[:-1], text2[:-1]) + 1\n",
    "        else:\n",
    "            len1 = self.longestCommonSubsequence(text1[:-1], text2)\n",
    "            len2 = self.longestCommonSubsequence(text1, text2[:-1])\n",
    "            result = max(len1, len2)\n",
    "        self._memos[(len(text1), len(text2))] = result\n",
    "        return result\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        return recur(text1, text2)\n",
    "\n",
    "\n",
    "def recur(text1, text2):\n",
    "    m, n = len(text1), len(text2)\n",
    "\n",
    "    @functools.lru_cache(m * n)\n",
    "    def f(i, j):\n",
    "        if i == -1 or j == -1:\n",
    "            return 0\n",
    "        res = max(f(i - 1, j), f(i, j - 1))\n",
    "        if text1[i] == text2[j]:\n",
    "            res = max(res, 1 + f(i - 1, j - 1))\n",
    "        return res\n",
    "\n",
    "    return f(m - 1, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.memory = {}\n",
    "        def solve(text1, text2):\n",
    "            key = '{0}|{1}'.format(len(text1), len(text2))\n",
    "            if key in self.memory:\n",
    "                return self.memory[key]\n",
    "\n",
    "            if len(text1) == 0 or len(text2) == 0:\n",
    "                return 0, 0, 0\n",
    "\n",
    "            growth = True if text1[-1] == text2[-1] else False\n",
    "\n",
    "\n",
    "            length_text1, endl1, endl2 = solve(text1[:-1], text2)\n",
    "            if growth and endl2 != len(text2):\n",
    "                length_text1 += 1\n",
    "\n",
    "            length_text2, endr1, endr2 = solve(text1, text2[:-1])\n",
    "            if growth and endr1 != len(text1):\n",
    "                length_text2 += 1\n",
    "\n",
    "            end1 = 0\n",
    "            end2 = 0\n",
    "            length = None\n",
    "            if length_text1 > length_text2:\n",
    "                length = length_text1\n",
    "                if growth and endl2 != len(text2):\n",
    "                    end1 = len(text1)\n",
    "                    end2 = len(text2)\n",
    "                else:\n",
    "                    end1 = endl1\n",
    "                    end2 = endl2\n",
    "            else:\n",
    "                length = length_text2\n",
    "                if growth and endr1 != len(text1):\n",
    "                    end1, end2 = len(text1), len(text2)\n",
    "                else:\n",
    "                    end1, end2 = endr1, endr2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            length = max(length_text1, length_text2)\n",
    "            self.memory['{0}|{1}'.format(len(text1), len(text2))] = [length, end1, end2]\n",
    "\n",
    "            # print(\"[{0}, {1}]={2}\".format(text1[:-1], text2, length_text1), \"[{0}, {1}]={2}\".format(text1, text2[:-1], length_text2), '=>', text1, text2, 'length:', length)\n",
    "            return length, end1, end2\n",
    "\n",
    "        length, _, _ = solve(list(text1), list(text2))\n",
    "        # print('\\n'.join(['{0}:{1}'.format(key, value) for key, value in self.memory.items()]))\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m, n = len(text1), len(text2)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        parent = {}\n",
    "        \n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if text1[i - 1] == text2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                    parent[(i, j)] = (i - 1, j - 1, text1[i - 1])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "                    if dp[i - 1][j] > dp[i][j - 1]:\n",
    "                        parent[(i, j)] = (i - 1, j, \"\")\n",
    "                    else:\n",
    "                        parent[(i, j)] = (i, j - 1, \"\")\n",
    "                    \n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        F = {}\n",
    "        B = {}\n",
    "        l1 = len(text1)\n",
    "        l2 = len(text2)\n",
    "        for i in range(-1,l1):\n",
    "            F[i, -1] = 0\n",
    "        for j in range(-1,l2):\n",
    "            F[-1, j] = 0\n",
    "        for i in range(0, l1):\n",
    "            for j in range(0, l2):\n",
    "                if text1[i] == text2[j]:\n",
    "                    F[i, j] = F[i - 1, j - 1] + 1\n",
    "                    B[i, j] = 'upleft'\n",
    "                else:\n",
    "                    if F[i - 1, j] >= F[i, j - 1]:\n",
    "                        F[i, j] = F[i - 1, j]\n",
    "                        B[i, j] = 'up'\n",
    "                    else:\n",
    "                        F[i, j] = F[i, j - 1]\n",
    "                        B[i, j] = 'left'\n",
    "        return F[l1-1,l2-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        \n",
    "        @lru_cache(maxsize=None)\n",
    "        def memo_solve(p1, p2):\n",
    "            \n",
    "            # Base case: If either string is now empty, we can't match\n",
    "            # up anymore characters.\n",
    "            if p1 == len(text1) or p2 == len(text2):\n",
    "                return 0\n",
    "            \n",
    "            # Option 1: We don't include text1[p1] in the solution.\n",
    "            option_1 = memo_solve(p1 + 1, p2)\n",
    "            \n",
    "            # Option 2: We include text1[p1] in the solution, as long as\n",
    "            # a match for it in text2 at or after p2 exists.\n",
    "            first_occurence = text2.find(text1[p1], p2)\n",
    "            option_2 = 0\n",
    "            if first_occurence != -1:\n",
    "                option_2 = 1 + memo_solve(p1 + 1, first_occurence + 1)\n",
    "            \n",
    "            # Return the best option.\n",
    "            return max(option_1, option_2)\n",
    "                \n",
    "        return memo_solve(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        F = {}\n",
    "        B = {}\n",
    "        l1 = len(text1)\n",
    "        l2 = len(text2)\n",
    "        for i in range(l1):\n",
    "            F[i, 0] = 0\n",
    "            if text2[0] in text1[:i + 1]:\n",
    "                F[i, 0] += 1\n",
    "                B[i, 0] = 1\n",
    "        for j in range(l2):\n",
    "            F[0, j] = 0\n",
    "            if text1[0] in text2[:j + 1]:\n",
    "                F[0, j] += 1\n",
    "                B[0, j] = 1\n",
    "        for i in range(1, l1):\n",
    "            for j in range(1, l2):\n",
    "                if text1[i] == text2[j]:\n",
    "                    F[i, j] = F[i - 1, j - 1] + 1\n",
    "                    B[i, j] = 'upleft'\n",
    "                else:\n",
    "                    if F[i - 1, j] >= F[i, j - 1]:\n",
    "                        F[i, j] = F[i - 1, j]\n",
    "                        B[i, j] = 'up'\n",
    "                    else:\n",
    "                        F[i, j] = F[i, j - 1]\n",
    "                        B[i, j] = 'left'\n",
    "        return F[l1-1,l2-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "\n",
    "        dp_dict = {}\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if i==len(text1) or j ==len(text2):\n",
    "                return 0\n",
    "            \n",
    "            key = '{}_{}'.format(i, j)\n",
    "\n",
    "            if key in dp_dict:\n",
    "                return dp_dict[key]\n",
    "\n",
    "            if text1[i] == text2[j]:\n",
    "                res = dfs(i+1,j+1)+1\n",
    "                dp_dict[key] = res\n",
    "\n",
    "            else:\n",
    "                res = max(dfs(i+1,j),dfs(i,j+1))\n",
    "                dp_dict[key] = res\n",
    "            return res\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        s=text1\n",
    "        t=text2\n",
    "\n",
    "        # # ！！！！ 超长返回-1\n",
    "        # if len(s)*len(t)>10000000:\n",
    "        #     return -1\n",
    "        \n",
    "        n=len(s)\n",
    "        m=len(t)\n",
    "        \n",
    "        def snake(x,y):\n",
    "            i=0\n",
    "            while x+i<n and y+i<m:\n",
    "                if s[x+i]!=t[y+i]:\n",
    "                    break\n",
    "                i+=1\n",
    "            return i\n",
    "        \n",
    "        cache={'0,0':(snake(0,0),snake(0,0))}\n",
    "        target_dk = None\n",
    "        flag=0\n",
    "        for d in range(1,n+m+1):\n",
    "            if flag==1: # ！！！跳出二层循环\n",
    "                break\n",
    "            for k in range(-d,d+1,2):\n",
    "                p1 = cache.get(str(d-1)+','+str(k-1))\n",
    "                p2 = cache.get(str(d-1)+','+str(k+1))\n",
    "                if p1 and p2:\n",
    "                    p = max((p1[0]+1,p1[1]),(p2[0],p2[1]+1))\n",
    "                elif p1 and not p2:\n",
    "                    p = (p1[0]+1,p1[1])\n",
    "                elif not p1 and p2:\n",
    "                    p = (p2[0],p2[1]+1)\n",
    "                else:\n",
    "                    continue\n",
    "                if not (p[0]<n+1 and p[1]<m+1):\n",
    "                    continue\n",
    "                    \n",
    "                sk = snake(p[0],p[1])\n",
    "                p_dk = (p[0]+sk,p[1]+sk)\n",
    "                if p_dk == (n,m):\n",
    "                    target_dk = (d,k)\n",
    "                    flag=1 # ！！！跳出二层循环\n",
    "                    break\n",
    "                cache[str(d)+','+str(k)] = p_dk\n",
    "        if flag==0: # ！！！\n",
    "            target_dk = (0,0)\n",
    "        # # 回溯\n",
    "        # vertices=[(n,m)]\n",
    "        # k = target_dk[1]\n",
    "        # for d in range(target_dk[0],0,-1):\n",
    "        #     p1 = cache.get(str(d-1)+','+str(k-1))\n",
    "        #     p2 = cache.get(str(d-1)+','+str(k+1))\n",
    "        #     if p1 and p2:\n",
    "        #         if p1[0]==n or (p2[1]!=m and p2[0]>p1[0]):\n",
    "        #             k = k+1\n",
    "        #             vertices.append(p2)\n",
    "        #         else:\n",
    "        #             k = k-1\n",
    "        #             vertices.append(p1)\n",
    "        #         continue\n",
    "        #     elif p1:\n",
    "        #         k = k-1\n",
    "        #         vertices.append(p1)\n",
    "        #     else:\n",
    "        #         k = k+1\n",
    "        #         vertices.append(p2)\n",
    "        # vertices.reverse()\n",
    "        \n",
    "        # return target_dk,vertices\n",
    "        return int((m+n-target_dk[0])/2)     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.text1,self.text2 = text1,text2\n",
    "        return self.dp(0,0)\n",
    "    @cache# return 是text1[i:] text2[j:]后续的长公共子序列\n",
    "    def dp(self,i,j):\n",
    "        if j==len(self.text2):\n",
    "            return 0\n",
    "        if i==len(self.text1):\n",
    "            return 0\n",
    "        if self.text1[i]==self.text2[j]:\n",
    "            return self.dp(i+1,j+1)+1\n",
    "        else:\n",
    "            return max(self.dp(i,j+1),self.dp(i+1,j))\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        self.t1 = text1\n",
    "        self.t2 = text2\n",
    "        result = self.dfs(len(self.t1)-1,len(self.t2)-1)\n",
    "        return result\n",
    "    @lru_cache(None)\n",
    "    def dfs(self,i,j):\n",
    "        if i==-1 or j==-1:\n",
    "            return 0\n",
    "        r1 = self.dfs(i-1,j)\n",
    "        r2 = self.dfs(i,j-1)\n",
    "        r3 = self.dfs(i-1,j-1)+int(self.t1[i]==self.t2[j])\n",
    "        return max(r1,r2,r3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        # dp函数\n",
    "        def dp(s1, i1, s2, i2):\n",
    "            n1 = len(s1)\n",
    "            n2 = len(s2)\n",
    "\n",
    "            # base case\n",
    "            if i1 >= n1 or i2 >= n2:\n",
    "                return 0\n",
    "            \n",
    "            # 状态\n",
    "            key = (i1, i2)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            \n",
    "            # 选择\n",
    "            if s1[i1] == s2[i2]:\n",
    "                res = 1 + dp(s1, i1+1, s2, i2+1)\n",
    "            else:\n",
    "                res = max(dp(s1, i1+1, s2, i2), dp(s1, i1, s2, i2+1))\n",
    "            \n",
    "            memo[key] = res\n",
    "            return res\n",
    "\n",
    "        memo = dict()\n",
    "        return dp(text1, 0, text2, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        if not text1 or not text2:\n",
    "            return 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i,j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            if text1[i] == text2[j]:\n",
    "                res = max(res, dp(i - 1,j - 1) + 1)\n",
    "            else:\n",
    "                res = max(res, dp(i - 1, j - 1), dp(i - 1, j), dp(i, j - 1))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        \n",
    "        return dp(len(text1) - 1, len(text2) - 1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(t,s):\n",
    "            if t< 0 or s < 0:\n",
    "                return 0\n",
    "            if text1[t] == text2[s]:\n",
    "                return dfs(t-1,s-1)+1\n",
    "            return max(dfs(t-1,s-1), dfs(t-1,s), dfs(t,s-1))\n",
    "        return dfs(len(text1)-1, len(text2)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        def dp(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if text1[i] == text2[j]:\n",
    "                return dp(i - 1, j - 1) + 1 \n",
    "            else:\n",
    "                memo[(i, j)] = max(dp(i - 1, j), dp(i, j - 1))\n",
    "                return memo[(i, j)]\n",
    "            \n",
    "        i = len(text1) - 1\n",
    "        j = len(text2) - 1\n",
    "        memo = {}\n",
    "        return dp(i, j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, s: str, p: str) -> int:\n",
    "    \n",
    "        m,n = len(s), len(p)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            if s[i] != p[j]:\n",
    "                return max(dfs(i, j - 1), dfs(i - 1, j))\n",
    "            return dfs(i - 1, j - 1) + 1\n",
    "        return dfs(m - 1,n - 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
